Multi-layer networks are networks in which several protocols may coexist atdifferent layers. The Pseudo-Wire architecture provides encapsulation andde-capsulation functions of protocols over Packet-Switched Networks. In amulti-domain context, computing a path to support end-to-end services requiresthe consideration of encapsulation and decapsulation capabilities. It appearsthat graph models are not expressive enough to tackle this problem. In thispaper, we propose a new model of heterogeneous networks using Automata Theory.A network is modeled as a Push-Down Automaton (PDA) which is able to capturethe encapsulation and decapsulation capabilities, the PDA stack correspondingto the stack of encapsulated protocols. We provide polynomial algorithms thatcompute the shortest path either in hops or in the number of encapsulations anddecapsulations along the inter-domain path, the latter reducing manualconfigurations and possible loops in the path.
展开▼
